/*给你一个字符串 s，找到 s 中最长的回文子串。
*
* 输入：s = "babad"
* 输出："bab"
* 解释："aba" 同样是符合题意的答案。
* */

package Leetcode;

public class leetcode5 {

    public static void main(String[] args) {

        leetcode5 obj = new leetcode5();
        String s = "babad";
        System.out.println(obj.longestPalindrome(s));
    }

    public String longestPalindrome(String s){

        int len = s.length();
        if (len < 2){
            return s;
        }
        boolean[][] dp = new boolean[len][len];
        int max = 0, left = 0, right = 0;
        for (int r = 1;r < len;r++){
            for (int l = 0;l < r;l++){
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])){
                    dp[l][r] = true;
                    if (r - l + 1 > max){
                        left = l;
                        right = r;
                        max = r - l + 1;
                    }
                }
            }
        }
        return s.substring(left, right + 1);
    }
}
